﻿#include <iostream>
#include <algorithm>

using namespace std;

static int howManyBoatsAtLeast(int* arr, const size_t arrSize, int limit)
{
	sort(arr, arr + arrSize, less<int>());
	if (arr[arrSize - 1] > limit) return 0;

	int middle = limit / 2;
	if (arr[arrSize - 1] <= middle)
	{
		return (arrSize + 1) / 2;
	}

	if (arr[0] > middle)
	{
		return arrSize;
	}

	int l;
	int r;
	for (int i = arrSize - 1; i >= 0; i--)
	{
		if (arr[i] <= middle)
		{
			l = i;
			r = l + 1;
			break;
		}
	}

	// ≤middle数字无法匹配>middle数字的个数
	int canNotMatchCount = 0;
	// 能配对成功的个数
	int canMatchCount = 0;
	while (l >= 0 && r < arrSize)
	{
		if (arr[l] + arr[r] <= limit)
		{
			++canMatchCount;
			--l;
			++r;
		}
		else
		{
			++canNotMatchCount;
			--l;
		}
	}

	int lRemain = l + 1;
	int rRemain = arrSize - r;
	return lRemain + rRemain + canMatchCount + (canNotMatchCount + 1) / 2;
}

/**
 * 给定一个数组arr，长度为N且每个值都是正数，代表N个人的体重。再给定一个正数limit，代表一艘船的载重。以下是坐船规则：
 * 1. 每艘船最多只能坐2人
 * 2. 乘客的体重和不能超过limit
 * 
 * 返回如果同时让这N个人过河最少需要多少条船。
 * 
 * 思路：
 * 将arr的元素按照从小到大排序，并划定一个中间线middle=limit/2
 * 1. 如果有一个数字>limit，则需要的船只总是是0，就是无论如何也无法将所有人都过河
 * 2. 如果所有的数字都≤middle, 则需要的船只总数是(N+1)/2, 即N/2的向上取整。
 * 3. 如果所有的数字都>middle，则需要的船只总数是N
 * 4. 如果是其他情况，则使用双指针方法
 * 
 * 举例：arr=[1,2,2,3,4,4,4,5,5,6,6,6,7,8,9,9], limit=10，其中，arr是经过排序的
 * 则middle=limit/2=5
 * 
 * 刚开始：L指向≤middle的最右元素, R指向>middle的最左元素
 *        1   2   2   3   4   4   4   5   5   6   6   6   7   8   9   9
 *                                        ↑   ↑
 *                                        L   R
 * 
 * 若L与R指向的数字相加≤limit，则记录一艘船，设这种情况的船的数量为a，a++，然后L左移，R右移；
 * 若L与R指向的数字相加>limit, 则计数，设为b，b++，L左移。
 * 
 * 若L先到达-1位置，则进行结算，R和它的右侧没有结算的数字，一个数字一艘船，然后与a相加，与(b+1)/2相加得到最终答案；
 * 若R先到达arr.Length位置，则进行结算，L和其左侧的数字的总数/2向上取整,加(b+1)/2，然后再加a得到最终答案。
 */
int main_howmanyBoatsNeeded()
{
	//int arr[] = { 3,4,6,7,6,6,8,9,1,9,2,4,5,2,4,5, };
	int arr[] = { 1,1,3,3,3,4,4,5,5,5,7,7,9,9,9 };
	auto arrSize = sizeof(arr) / sizeof(int);
	int limit = 10;

	int boatsCount = howManyBoatsAtLeast(arr, arrSize, limit);
	printf("%d", boatsCount);

	return 0;
}